#include<iostream>
#include<vector>
#include<string>
using namespace std;


//647.回文子串
int countSubstrings(string s){
    int n = s.size();

    //状态表示 dp[i][j]表示以i位置字符为开头，j位置字符为结尾的子串是否是回文子串
    //状态表中会存储每个子串是否是回文子串的信息
    vector<vector<bool>> dp(n, vector<bool>(n));

    int ret = 0;
    //填表顺序 从最后一行到第一行 因为当前状态值需要用到左下角的状态值
    for (int i = n - 1; i >= 0; i--){
        for (int j = i; j < n; j++){
            if(s[i]==s[j]){
                if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){
                    dp[i][j] = true;
                }
            }

            //如果当前子串是回文子串，个数加一
            if (dp[i][j] == true){
                ret += 1;
            }
        }
    }

    //返回值
    return ret;
}

//5.最长回文子串
string longestPalindrome(string s){
    int n = s.size();

    //状态表示 dp[i][j]表示以i位置字符为开头，j位置字符为结尾的子串是否是回文子串
    //状态表中会存储每个子串是否是回文子串的信息
    vector<vector<int>> dp(n, vector<int>(n));

    int maxlen = 0;
    int begin = 0;
    //填表
    for (int i = n - 1; i >= 0; i--){
        for (int j = i; j < n; j++){
            if(s[i]==s[j]){
                if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){
                    dp[i][j] = true;
                }
            }

            if (dp[i][j] == true){
                //更新最长的长度和开头下标
                maxlen = max(maxlen, j - i + 1);
                if (maxlen == j - i + 1){
                    begin = i;
                }
            }
        }
    }

    //返回值
    return s.substr(begin, maxlen);
}

//1745.分割回文串
bool checkPartitioning(string s){
    int n = s.size();

    //状态表示
    vector<vector<bool>> dp(n, vector<bool>(n));

    //填表
    for (int i = n - 1; i >= 0; i--){
        for (int j = i; j < n; j++){
            if (s[i] == s[j]){
                if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){
                    dp[i][j] = true;
                }
            }
        }
    }

    //返回值 分割成三个回文子串 [0,i-1],[i,j],[j+1,n-1]
    for (int i = 1; i < n - 1; i++){
        for (int j = i; j < n - 1; j++){
            if (dp[0][i - 1] == true && dp[i][j] == true && dp[j + 1][n - 1] == true){
                return true;
            }
        }
    }
    return false;
}


//分割回文串2
int minCut(string s){
    int n = s.size();

    //先获取每个子串是否是回文子串的信息,存放到二维状态表中
    vector<vector<bool>> dp(n, vector<bool>(n));
    for (int i = n - 1; i >= 0; i--){
        for (int j = i; j < n; j++){
            if (s[i] == s[j]){
                if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){
                    dp[i][j] = true;
                }
            }
        }
    }

    //状态表示 min_cut[i]表示[0,i]区间内的子串，分割成回文子串最小的分割次数
    //初始化 因为要去前状态中的最小值，所以状态表中全部先初始化为最大值
    vector<int> min_cut(n, INT_MAX);

    //填表
    for (int i = 0; i < n; i++){
        if (dp[0][i] == true){
            min_cut[i] = 0;
        }
        else{
            for (int j = i; j > 0; j--){
                if (dp[j][i] == true){
                    //状态转移方程
                    min_cut[i] = min(min_cut[j - 1] + 1, min_cut[i]);
                }
            }
        }
    }

    //返回值
    return min_cut[n - 1];
}


//516.最长回文子序列的长度
int longestPalindromeSubseq(string s){
    int n = s.size();

    //状态表示 dp[i][j]表示[i,j]区间内，最长回文子序列的长度
    vector<vector<int>> dp(n, vector<int>(n));

    //填表 从上往下，其中每一行从左往右
    for (int i = n - 1; i >= 0; i--){
        for (int j = i; j < n; j++){
            //如果当前两个位置的字符相等，找区间内的最长回文子序列的长度
            if (s[i] == s[j]){
                if (i == j){
                    dp[i][j] = 1;
                }
                else if (i + 1 == j){
                    dp[i][j] = 2;
                }
                else{
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }
            }
            //如果当前两个位置的字符不相等，找[i+1,j]和[i,j-1]两个区间内的最长回文子序列的长度
            else{
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
    }

    //返回值
    return dp[0][n - 1];
}

//1312.让字符串成为回文串的最少插入次数
int minInsertions(string s){
    int n = s.size();

    //状态表示 dp[i][j]表示[i,j]区间内字符串成为回文串的最少插入次数
    vector<vector<int>> dp(n, vector<int>(n));

    //填表 从最后一行到第一行，其中每一行从左往右
    for (int i = n - 1; i >= 0; i--){
        for (int j = i; j < n; j++){
            if (s[i] == s[j]){
                if (i == j || i + 1 == j){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            else{
                dp[i][j] = min(dp[i][j - 1] + 1, dp[i + 1][j] + 1);
            }
        }
    }

    //返回值
    return dp[0][n - 1];
}

int main(){

    return 0;
}